{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2-3查找树定义\n",
    "\n",
    "       为了解决二叉查找树的不平衡，2-3树孕育而生，2-3树能够很好的实现树的平衡。\n",
    "       为啥能保持平衡，因为你每个节点可以多存一个数据嘛，而且有3个子节点的话，能将数据分布的更加均匀。\n",
    "<font color=red>根节点到每一个为空节点的距离都相同。</font>\n",
    "\n",
    " \n",
    "       和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下： \n",
    "   \n",
    "       1）要么为空，要么： \n",
    "       2）对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，右节点也是一个2-3节点，所有的值比key要大。 \n",
    "       3）对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个根节点中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个根节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个根节点中的最大的key还要大。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " 2-3查找树的性质\n",
    "\n",
    "       1）如果中序遍历2-3查找树，就可以得到排好序的序列； \n",
    "       2）在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。（这也是平衡树中“平衡”一词的概念，根节点到叶节点的最长距离对应于查找算法的最坏情况，而平衡树中根节点到叶节点的距离都一样，最坏情况也具有对数复杂度。） \n",
    "      2-3树的查找效率与树的高度是息息相关的。 \n",
    "\n",
    "      距离来说，对于1百万个节点的2-3树，树的高度为12-20之间，对于10亿个节点的2-3树，树的高度为18-30之间。 \n",
    "      插入来说，只需要常数次操作即可完成，因为他只需要修改与该节点关联的节点即可，不需要检查其他节点，所以效率和查找类似。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"2-3树.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2-3树的插入\n",
    "\n",
    "#### 1、向2-节点插入key\n",
    "\n",
    "    如果是向一个2节点插入新建，直接变成3-节点，所有空链到根节点的高度不变。\n",
    "\n",
    "插入K的过程\n",
    "\n",
    "    K<L,所以去L的左子树中去查找，L的左子树是空，所以未命中，将K插入，把包含L节点的2-节点直接变成3-节点\n",
    "<img src=\"23树插入1.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2、向一颗只含有3-节点的树种插入新键\n",
    "\n",
    "<img src=\"23树插入2.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3、向一个父节点是2-节点的3-节点插入新键：插入Z\n",
    "\n",
    "    假设未命中查找结束于一个3-节点，而且该3-节点的父节点是2-节点。我们的做法是新键一个4-节点，并将4-节点分解，其中，中键移动到原来的父节点中，也就是原来的2-节点变成3-节点。\n",
    "    \n",
    "<img src=\"23树插入3.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4、向一个父节点是3-节点的3-节点插入新键：插入D\n",
    "\n",
    "    假设未命中查找结束于一个3-节点，而且该3-节点的父节点是3-节点。我们的做法是新键一个4-节点，并将4-节点分解，其中，中键移动到原来的父节点中，也就是原来的3-节点变成4-节点，然后再进行一次分解，一直向上，直到碰到一个2-节点，或者3-节点的根节点。\n",
    "\n",
    "<img src=\"23树插入4.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,key):\n",
    "        \"\"\"将key存到key1中\"\"\"\n",
    "        self.key1 = key\n",
    "        self.key2 = None\n",
    "        self.left = None\n",
    "        self.mid = None\n",
    "        self.right = None\n",
    "    \n",
    "    def isLeaf(self):\n",
    "        \"\"\"没有儿子\"\"\"\n",
    "        return self.left is None and self.mid is None and self.right is None\n",
    "    \n",
    "    def isFull(self):\n",
    "        \"\"\"只看key2是不是为空\"\"\"\n",
    "        return self.key2 is not None\n",
    "    \n",
    "    def hashKey(self,key):\n",
    "        \"\"\"key是否在本节点\"\"\"\n",
    "        if self.key1 == key or self.key2 is not None and self.key2 == key:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    def getChild(self,key):\n",
    "        \"\"\"返回合适的子节点\"\"\"\n",
    "        if key < self.key1:\n",
    "            return self.left\n",
    "        elif self.key2 is None:\n",
    "            return self.mid\n",
    "        elif key < self.key2:\n",
    "            return self.mid\n",
    "        else:\n",
    "            return self.right\n",
    "        \n",
    "\n",
    "class Tree_2_3:\n",
    "    def __init__(self):\n",
    "        self._root = None\n",
    "    \n",
    "    def get(self,key):\n",
    "        if self._root is None:\n",
    "            return None\n",
    "        else:\n",
    "            return self._get(self._root, key)\n",
    "        \n",
    "    def _get(self, node, key):\n",
    "        if node is None:\n",
    "            return None\n",
    "        elif node.hashKey(key):\n",
    "            \"\"\"是否本节点\"\"\"\n",
    "            return node\n",
    "        else:\n",
    "            child = node.getChild(key)\n",
    "            return self._get(child, key)\n",
    "            \n",
    "    def put(self, key):\n",
    "        if self._root is None:\n",
    "            self._root = Node(key)\n",
    "        else:\n",
    "            p_key, p_ref = self._put(self._root, key)\n",
    "            if p_key is not None:\n",
    "                new_node = Node(key)\n",
    "                new_node.left = self._root \n",
    "                new_node.mid = p_ref  # 返回的需要被调整的节点肯定比_root节点要大\n",
    "                self._root = new_node # 返回的是中间的值。\n",
    "            \n",
    "    def _put(self, node, key):\n",
    "        \"\"\"找到合适的put位置\"\"\"\n",
    "        if node.hashKey(key):\n",
    "            \"\"\"已存在\"\"\"\n",
    "            return None,None\n",
    "        elif node.isLeaf():\n",
    "            \"\"\"叶子节点插入\"\"\"\n",
    "            return self._addToNode(node, key, None)\n",
    "        else:\n",
    "            \"\"\"非叶子节点插入：\n",
    "                    根据key找到子节点，对子节点进行插入。\n",
    "            \"\"\"\n",
    "            child = node.getChild(key)\n",
    "            p_key, p_ref = self._put(child, key)\n",
    "            if p_key is None:\n",
    "                \"\"\"表示，没有爸爸节点需要调整\"\"\"\n",
    "                return None, None\n",
    "            else:\n",
    "                return self._addToNode(node, p_key, p_ref)\n",
    "        \n",
    "    def _addToNode(self, node, key, p_ref):\n",
    "        if node.isFull():\n",
    "            \"\"\"  2、如果叶子节点满了，那就要split。 p_ref传的是None就表示是第2种情况，只有一个3节点（根节点）\n",
    "            否则就是3、和 4\n",
    "            \"\"\"\n",
    "            return self._splitNode(node, key, p_ref)\n",
    "        else:\n",
    "            \"\"\"  1、如果叶子节点没满，那就直接存入叶子结点，也就是2节点变3节点\"\"\"\n",
    "            if key < node.key1:\n",
    "                node.key2 =node.key1\n",
    "                node.key1 = key\n",
    "                if p_ref is not None:\n",
    "                    node.right = node.mid\n",
    "                    node.mid = p_ref\n",
    "            else:\n",
    "                node.key2 = key\n",
    "                if p_ref is not None:\n",
    "                    node.right = p_ref\n",
    "            return None, None\n",
    "        \n",
    "    def _splitNode(self, node, key, p_ref):\n",
    "        new_node = Node(None)\n",
    "        if key < node.key1:\n",
    "            \"\"\"左\"\"\"\n",
    "            p_key = node.key1\n",
    "            node.key1 = key\n",
    "            new_node.key1 = node.key2\n",
    "            if p_ref is not None:\n",
    "                new_node.left = node.mid\n",
    "                new_node.mid = node.right\n",
    "                node.mid = p_ref\n",
    "        elif key < node.key2:\n",
    "            \"\"\"中\"\"\"\n",
    "            p_key = key\n",
    "            new_node.key1 = node.key2\n",
    "            if p_ref is not None:\n",
    "                new_node.left = p_ref\n",
    "                new_node.mid = node.right\n",
    "        else:\n",
    "            \"\"\"右\"\"\"\n",
    "            p_key = node.key2  # 把key2 返回，往上拱，作为父节点\n",
    "            new_node.key1 = key # 新节点的key1 是右节点\n",
    "            if p_ref is not None:\n",
    "                new_node.left = node.right\n",
    "                new_node.mid = p_ref\n",
    "        node.key2 = None  # 本分裂节点会变成2节点，所以 key2 = None\n",
    "        return p_key,new_node\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    23树生长轨迹1\n",
    "<img src = \"23树生长轨迹1.png\">\n",
    "\n",
    "\n",
    "    23树生长轨迹2\n",
    "    \n",
    "<img src = \"23树生长轨迹2.png\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意哦，只在叶子节点插入。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
